
/**
 * 
 * 
 * 数大雁
 * 题目描述

一群大雁往南飞，给定一个字符串记录地面上的游客听到的大雁叫声，请给出叫声最少由几只大雁发出。

具体的：

大雁发出的完整叫声为”quack“，因为有多只大雁同一时间嘎嘎作响，所以字符串中可能会混合多个”quack”。
大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成，或者没有找到一只大雁，请返回-1。


输入描述
一个字符串，包含大雁quack的叫声。1 <= 字符串长度 <= 1000，字符串中的字符只有’q’, ‘u’, ‘a’, ‘c’, ‘k’。

输出描述
大雁的数量

用例
输入	quackquack
输出	1
说明	无
输入	qaauucqckk
输出	-1
说明	无
输入	quacqkuac
输出	1
说明	无
输入	qququaauqccauqkkcauqqkcauuqkcaaukccakkck
输出	5
说明	无
 * 
 */

import java.util.Scanner;

/**
  
 *
 * 题目解析
首先看一个例子：



对于标黄的"uack"，我们应该归属于哪一个绿色的"q"呢？

如果归属于第一个绿色"q"，那么该例子就至少有两只大雁
如果归属于第二个绿色"q"，那么该例子就至少有一只大雁
这里的两个"q"更准确的描述是：

第一个"q"是前一次完整叫声中的第一个"q"
第二个"q"是前一次完整叫声后的第一个"q"


下面我对这两种理解都做了实现

归属于第一个"q"解法（90%通过率）
此解法虽然看起来和LeetCode - 1419 数青蛙_伏城之外的博客-CSDN博客

很像，但是难度却要大于leetcode这道题，原因是

大雁会依次完整发出”quack”，即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
而leetcode数青蛙

如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。
leetcode这题，如果存在不完整或者不按顺序的叫声，则直接返回-1。结束程序。

而本题，则对于不完整或者不按顺序的叫声，只是不予计数，后面还要继续统计。

比如 quaquck

如果按照leetcode数青蛙逻辑来做的话，结果应该返回-1。

而本题逻辑却需要返回1。

leetcode难度小的原因是，不需要考虑剔除不完整或者不按顺序的叫声。

而本题难度大的原因是，需要考虑剔除不完整或者不按顺序的叫声。

我的解题思路是，求出每个叫声quack的区间范围，即一次叫声的：[q索引位置，k索引位置]。

实现是：从左到右遍历叫声字符串，遇到q，则将其索引位置加入缓存中，

遇到u，则判断u出现的次数是否超过了q出现的次数，若是则忽略本次u，否则u次数++

遇到a，则判断a出现的次数是否超过了u出现的次数，若是则忽略本次a，否则a次数++

遇到c，则判断c出现的次数是否超过了a出现的次数，若是则忽略本次c，否则c次数++

遇到k，则判断c次数是否大于等于1，若否，则忽略本次k，否则出队第一个q出现索引和本次k的索引，组合成一个区间范围，然后u--,a--,c--，表示取出了一次叫声。

按照上面逻辑，我们可以剔除掉不完整或者不按顺序的叫声，并且获得每个合法叫声的区间范围。

接下来就是遍历每一个区间，和后面区间比较，看是否有交集，若有，则记录交集数。

最终最大的交集数就是最多大雁数。

下图是用例3：qququaauqccauqkkcauqqkcauuqkcaaukccakkck 


第二种解题思路


归属于第二个"q"解法
此解法思路很简单，即假设每只大雁都连续不断的叫，即某只大雁叫完一次后，接着叫

我们以题目自带的用例4为例：



其中一种颜色标记，就是一只大雁的多次叫声，比如黄色标记，就相当于一只大雁叫了三声quack，这三声quack是不交叉的，因此可以认为是同一只大雁叫的。

这里其实有贪心思维的存在，即认为每个大雁都会发出多次叫声，只要存在多次不交叉的叫声，即认为是一只大雁发出的，这样最终就可以得到最少大雁数量。

具体实现时，需要对输入的字符串进行多轮遍历，每轮遍历确认一只大雁，并将该大雁的多次叫声对应的位置标记为used，这样到下一轮遍历时，就不会造成多个大雁使用同一个叫声。

  */
public class 数大雁 {
    
    public static void main(String[] args) {

        try{

            Scanner scanner = new Scanner(System.in);
            String voiceStr = scanner.nextLine();

            //大雁的数量
            int bridCount = 0;


            char[] voiceChars = voiceStr.toCharArray();
            
            while (find(voiceChars)) {

                bridCount++;
            }

            System.out.println((bridCount <=0)? "-1": ""+bridCount);


        }catch(Exception e){
            e.printStackTrace();

        }
    }

    private static boolean find(char[] voiceChars){

        boolean isFind = false;

        //大雁叫声
        String voiceTemp = "quack";
        char voiced = 'I';  //标记已经记录过叫声的字符
        //记录一个完整的大雁叫声的下标，标记一个完整叫声后，把对应的字符设置成''
        int[]  voicePosition = new int[voiceTemp.length()];
        int voiceIndex = 0; //voicePosition 数组下标从 0 开始，找到voiceTemp对应字符则 ++

        for(int i=0; i<voiceChars.length; i++){

            if(voiceChars[i] == voiceTemp.charAt(voiceIndex)){

                //记录找到叫声字符的下标，并记录
                voicePosition[voiceIndex++] = i;
            }

            if(voiceIndex == 5){

                //已经完整记录一个 quack 叫声
                isFind = true;

                //根据 voicePosition 标记的下标 把对应字符设置成

                for(int position: voicePosition){
                    voiceChars[position] = voiced;
                    
                }

                //并且重置voiceIndex 以便寻找下一个
                voiceIndex = 0;
            }

        }

        return isFind;
    }
}
